#include<vector>
using namespace std;
class Solution {
    public:
        int reversePairs(vector<int>& record) {
            //思路：左统计+左排序+右统计+右排序+一左一右+排序
            return mergesort(record,0,record.size()-1);
        }
        int tmp[50100];
        int mergesort(vector<int>& record,int left ,int right){
            //处理边界情况
            if(left >= right)   return 0;
            int ret = 0,middle = left+(right-left)/2;
            //左统计+左排序+右统计+右排序
            ret += mergesort(record,left,middle);
            ret += mergesort(record,middle+1,right);
            //一左一右+排序
            int cur1 =  left,cur2 = middle+1,i = 0;
            while(cur1 <= middle && cur2 <= right){
                if(record[cur1] <= record[cur2]){
                    tmp[i++]= record[cur1++]; 
                }else{
                    ret += middle-cur1+1 ;
                    tmp[i++] = record[cur2++];
                }
            }
            while(cur1<=middle) tmp[i++] = record[cur1++];
            while(cur2<=right)  tmp[i++] = record[cur2++];
            for(int j = left ; j<= right ;j++){
                record[j] = tmp[j-left];
            }
    
            return ret;
        }
    };